/*
https://leetcode.cn/problems/number-of-digit-one/submissions/573837044/
数字1的个数
数位dp
*/
class Solution {
public:
    int onlyn(int n){
        int count=0;
        int j = n;
        while(j>0){
            if(j%10==1)
                count++;
            j=j/10;
        }
        return count;
    }

    int countDigitOne(int n) {
        
        if(n<=0)
            return 0;
        else if(n<10)
            return 1;
        int a=n/10;
        int b=n%10;
        return (countDigitOne(a-1) * 10) + (a) + (onlyn(a) * (b+1)) + (b==0?0:1);
    }
};